package Leetcode.DayTest;

/**
 * 循环赛日程表：有n = 2^k个运动员要进行网球循环赛
 * 赛程表满足：
 * 每个选手必须与其他n-1个选手各赛一次
 * 每个选手一天只能参赛一次
 * 循环赛在n-1天内结束
 *
 * 解题思路：
 * 将比赛日程表设计成一个n行和n-1列的表，第i行，第j列分别填入第i个选手在第j天所遇到的选手
 * 栗子：
 * 4个选手
 * ---------
 * |1|2|3|4|
 * ---------
 * |2|1|4|3|
 * ---------
 * |3|4|1|2|
 * ---------
 * |4|3|2|1|
 * ---------
 * 分治思想：将所有区域看成四块，区域1：(0,i) 区域2：(0,r+i) 区域3：(r,i) 区域4：(r,r+i)
 *  递归执行的是区域1拷贝到区域4，区域2拷贝到区域3
 * ---------
 * | 1 | 2 |
 * ---------
 * | 3 | 4 |
 * ---------
 *
 */
public class Roundrobin {
    public static int[][] table(int k){
        int n = 1<<k;
        int[][] a = new int[n][n];
        //构造赛程表第一行数据
        for(int i = 0; i<n;i++)
            a[0][i] = i+1;
        //采用分治算法，构造整个赛程表
        for (int r = 1; r < n; r *= 2) {
            for (int i = 0; i < n; i += 2 * r) {
                copy(a, r, r + i, 0, i, r);
                copy(a, r, i, 0, r + i, r);
            }
        }
        return a;
    }

    private static void copy(int[][] targetArray, int targetX, int targetY,
                                     int sourceX, int sourceY, int subArraySize) {
        for (int i = 0; i < subArraySize; i++) {
            for (int j = 0; j < subArraySize; j++) {
                targetArray[targetX + i][targetY + j] = targetArray[sourceX + i][sourceY + j];
            }
        }
    }

    public static void main(String[] args) {
        int[][] a = table(3);
        for (int[] ints : a) {
            for (int j = 0; j < a[0].length; j++) {
                System.out.print(ints[j] + " ");
            }
            System.out.println();
        }
    }

}